package July;

/**
 * @author:gao
 * @date:2020/7/6
 * @time:8:15
 * @version:0.0.1
 * @description:none
 */


//63. 不同路径 II
public class UniquePathsWithObstacles {
}

//搜索，超时
//class Solution {
//    int ans = 0;
//    int[][] gird;
//    int row;
//    int col;
//    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//        gird = obstacleGrid;
//        row=gird.length;
//        col = gird[0].length;
//        if(gird[0][0]==1)return 0;
//        search(0,0);
//        return ans;
//    }
//    private void search(int x,int y){
//        if(x==row-1&&y==col-1){
//            ans++;
//            return;
//        }
//        //向右
//        if(x!=row-1&&gird[x+1][y]==0){
//            search(x+1,y);
//        }
//        //向下
//        if(y!=col-1&&gird[x][y+1]==0){
//            search(x,y+1);
//        }
//    }
//}


//dp二维数组版本
//class Solution {
//    public int uniquePathsWithObstacles(int[][] grid) {
//        int row=grid.length;
//        int col = grid[0].length;
//        if(grid[0][0]==1) return 0;
//        int[][] dp = new int[row][col];
//        boolean hasOne =false;
//        for(int i=0;i<col;i++){
//            if(!hasOne&&grid[0][i]!=1) dp[0][i]=1;
//            else{
//                hasOne=true;
//                dp[0][i]=0;
//            }
//        }
//        hasOne =false;
//        for (int i = 1; i < row; i++) {
//            if(!hasOne&&grid[i][0]!=1) dp[i][0]=1;
//            else{
//                hasOne=true;
//                dp[i][0]=0;
//            }
//        }
//        for (int i = 1; i <row ; i++) {
//            for (int j = 1; j < col; j++) {
//                if(grid[i][j]==1) dp[i][j]=0;
//                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
//            }
//        }
//        return dp[row-1][col-1];
//    }
//}


//dp一维数组版本（题解）
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];//用数组保存每列的值

        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;  //0 0等于1有障碍，可以直接返回
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0) {
                    f[j] += f[j - 1];//这个时候f[j]保存的是dp[i-1][j]
                                    //f[j-1]保存的是dp[i][j-1]
                                    //直接相加
                }
            }
        }

        return f[m - 1];
    }
}
